package com.banyuan.array;

import java.util.Arrays;

public class ChaPaiIdeas {
    public static void main(String[] args) {

        /*方法1：
        1、再截取一个数之后，要保证这个数之前的数都是排好序的；
        2、将这个数与该数之前的数比较，找出比这个数大，但是这个数的前一个数比这个数小的值的下标；
        3、然后将截取的那个数的值用temp保留（因为之后的移动的操作会使截取的那个值丢失），然后将从这个
            下标开始到截取的那个值前一个值整体向后移动一位；
        4、将temp保存的截取的值赋值给下标位。

         */
        int[] arr1 = new int[]{9, 6, 7, 4, 8, 1, 2, 3, 5};
        for (int i = 1; i < arr1.length; i++) {

            //找到插入的位置，即该位置的元素大于截取位的元素，该位置的前一个数小于等于截取数；
            int j = i;//这样定义主要是为了满足边界条件，i=1的情况。
            while (j > 0) {
                j--;
               /* 这边的终止条件是下标的值小于等于截取值，由于截取之前的数列都是有序排列的，所以
                 上一个的值一定是大于截取值的，上一个值刚好满足了插入的要求，因此下标+1得到满足的值。
                 */
                if (arr1[j] <= arr1[i]) {
                    j++;
                    break;
                }
            }

            /*
             * 下面进行从下标位置一直到截取位的前一位，开始向后移动一位。
             * 主要的难点其实是截取位置的数会被覆盖掉，因此在开始移动前，要事先将该值保留下来。
             * 移动的过程是拿后边的数接收前面的数，如果从下标值开始接受则会发生错误。
             * */

            int temp = arr1[i];
            //从下标位到截取位后移的过程。
            while (i > j) {
                arr1[i] = arr1[i - 1];
                i--;
            }
            //将截取位的值赋给下标位。
            arr1[j] = temp;
        }

        System.out.println(Arrays.toString(arr1));
    }
}
